{
LANG : PASCAL
PROB : twohead
}

program TWOHEAD;
const
  fi = 'twohead.in';
  fo = 'twohead.out';
  maxm = 50001;
  max = 25000;
  limit = 5000000;
type
  stt = record
          c1, c2 : integer;
          h1, h2 : char;
        end;
var
  d : array[1..2*maxm] of stt;
  p : array[0..max+1] of longint;
  a : array[1..max] of byte;
  first : array[1..max] of integer;
  n, m, ngroup, best : longint;
  time : longint;

procedure inp;
var
  i : longint;
begin
  read(n, m);
  for i := 1 to m do
  begin
    with d[i] do
    begin
      read(c1);
      if not seekeoln then read(h1);
      read(c2);
      if not seekeoln then read(h2);
    end;
    with d[i+m] do
    begin
      c1 := d[i].c2;
      c2 := d[i].c1;
      h1 := d[i].h2;
      h2 := d[i].h1;
    end;
  end;
end;

procedure swap(i, j : longint);
var
  temp : stt;
begin
  temp := d[i];
  d[i] := d[j];
  d[j] := temp;
end;

procedure sort1(l, r : longint);
var
  i, j, k : longint;
begin
  if l >= r then exit;
  i := l;
  j := r;
  k := d[l+random(r-l+1)].c1;
  repeat
    while d[i].c1 < k do inc(i);
    while d[j].c1 > k do dec(j);
    if i <= j then
    begin
      swap(i, j);
      inc(i); dec(j);
    end;
  until i > j;
  sort1(i, r); sort1(l, j);
end;

procedure sort2(l, r : longint);
var
  i, j, k : longint;
begin
  if l >= r then exit;
  i := l;
  j := r;
  k := d[l+random(r-l+1)].c2;
  repeat
    while d[i].c2 < k do inc(i);
    while d[j].c2 > k do dec(j);
    if i <= j then
    begin
      swap(i, j);
      inc(i); dec(j);
    end;
  until i > j;
  sort2(i, r); sort2(l, j);
end;

procedure init;
var
  i, j : longint;
begin
  sort1(1, 2*m);
  for i := 1 to 2*m do
    if d[i].h1 = 'B' then
    begin
      d[i].h1 := 'A';
      d[i].h2 := 'B';
    end;
  fillchar(p, sizeof(p), 0);
  for i := 1 to 2*m do inc(p[d[i].c1]);
  for i := 2 to n+1 do inc(p[i], p[i-1]);
  move(p[0], p[1], sizeof(p[0])*(n+1));
end;

function ok(k : longint) : boolean;
var
  i, j : longint;
begin
  ok := false;
  for i := p[k]+1 to p[k+1] do
  begin
    j := d[i].c2;
    if j < first[k] then continue;
    if d[i].h2 = 'A' then
    begin
      if a[j] = a[k] then exit;
    end
    else
    begin
      if a[j] <> a[k] then exit;
    end;
  end;
  ok := true;
end;

procedure try(k : longint);
begin
  if ngroup > best then exit;
  if time > limit then exit;
  inc(time);
  if k = n+1 then
  begin
    if ngroup < best then best := ngroup;
    exit;
  end;
  first[k] := first[k-1];
  a[k] := 1;
  if ok(k) then try(k+1);
  a[k] := 2;
  if ok(k) then try(k+1);
  inc(ngroup);
  first[k] := k;
  try(k+1);
  dec(ngroup);
end;

procedure process;
begin
  time := 0;
  ngroup := 0;
  best := 100000;
  if n = 1 then
  begin
    best := 1;
    exit;
  end;
  a[1] := 1;
  try(2);
end;

begin
  randomize;
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);
  inp;
  init;
  process;
  writeln(best);
  close(output);
  close(input);
end.